package com.zwh.algorithm.leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode2438 {

    private static final int MOD = 1000000007;
    /**
     * 2023-08-06 二的幂数组中查询范围内的乘积
     * todo 给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。
     *  同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。
     *  请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 109 + 7 取余 。
     * @param args
     */
    public static void main(String[] args) {
        int[] ints = productQueries(15, new int[][]{{0, 1}, {2, 2}, {0, 3}});
        System.out.println(Arrays.toString(ints));

    }
   public static int[] productQueries(int n, int[][] queries) {
        //二进制分解 例如 n=11，它的二进制表示为 (1011)，从低到高的第 0,1,3 个二进制位为 1，因此分解为 [1,2,8]。
       List<Integer> powers = new ArrayList<>();
       int rep = 1;
       while (n > 0) {
           if (n % 2 == 1) {
               powers.add(rep);
           }
           n /= 2;
           rep *= 2;
       }
        int[] answers = new int[queries.length];
        for (int i1 = 0; i1 < queries.length; i1++) {
           int[] query = queries[i1];
           int count = 1;
           for (int j = query[0]; j <= query[1]; j++) {
               count = (count * powers.get(j)) % MOD;
           }
           answers[i1] = count;
        }
        return answers;
   }
}
